package com.剑指offer.第六章;

import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * 有6棵小行星[4,5,-6,4,8,-5]，它们相撞之后最终剩下的3颗小行星[-6,4,8]
 */
public class 小行星碰撞 {

    public static List<Integer> resolve(Integer[] arr) {
        Stack<Integer> stack = new Stack<>();
        for (int i : arr) {
            // 发生碰撞的逻辑为 只有前一个为正数，当前为负数 才会发生碰撞
            while (!stack.empty() && stack.peek() > 0 && stack.peek() < -i) {
                stack.pop();
            }
            // 考虑相等的情况 并且方向相反
            if (!stack.empty() && i < 0 && stack.peek() == -i) {
                stack.pop();
            } else if (stack.empty() || i > 0 || stack.peek() < 0) {
                stack.push(i);
            }
        }
        return stack.stream().collect(Collectors.toList());
    }

    public static void main(String[] args) {

    }

}
